package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversal94 {
    //递归
    private List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root== null){return list;}
        inorder(root);
        return list;
    }
    private void inorder(TreeNode root){
        if(root==null){return;}
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }

    public List<Integer> inorderTraversal1(TreeNode root) {
        if(root== null){return list;}
        Stack<TreeNode> stack = new Stack<>();
        while (true){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            if(stack.isEmpty()){break;}
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}
